// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func main() {
	coins := []int{1, 2, 5} // 设置可用硬币
	amount := 26            // 设定目标金额

	// 调用 change() 函数以获取所需的最少硬币数量
	result := change(coins, amount)
	fmt.Printf("为目标金额为 %d 的找零所需的最少硬币数为：%d\n", amount, result)
}

func change(coins []int, amount int) int {
	// 初始化一个表来存储每个金额所需的最少硬币数量
	table := make([]int, amount+1)
	for i := range table {
		table[i] = amount + 1
	}
	table[0] = 0

	// 遍历每个硬币面额
	for _, coin := range coins {
		// 迭代每个金额直到目标金额
		for i := coin; i <= amount; i++ {
			// 如果使用这个硬币会导致需要更少的硬币，则更新表格
			table[i] = min(table[i], table[i-coin]+1)
		}
	}

	// 返回目标数量所需的最小硬币数量，如果不可能，则返回 -1
	if table[amount] > amount {
		return -1
	}
	return table[amount]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

//$ go run coinChange.go
//为目标金额为 26 的找零所需的最少硬币数为：6
